package com.xxd.algo.newcode.base01.class07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-01-12 09:52
 * @description:
 */
public class MedianQuick {

    public static class MedianHolder {
        private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapComparator());
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapComparator());

        public void addNumber(int num) {
            // 大于大根堆进小根堆
            if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }

            modifyTwoHeap();
        }

        private void modifyTwoHeap() {
            int maxHeapSize = this.maxHeap.size();
            int minHeapSize = this.minHeap.size();

            if (maxHeapSize - minHeapSize >= 2) {
                minHeap.add(maxHeap.poll());
            }

            if (minHeapSize - maxHeapSize >= 2) {
                maxHeap.add(minHeap.poll());
            }
        }

        public Double getMedian() {
            int maxHeapSize = this.maxHeap.size();
            int minHeapSize = this.minHeap.size();
            if (maxHeapSize + minHeapSize == 0) {
                return null;
            }

            Integer minHeapHead = this.minHeap.peek();
            Integer maxHeapHead = this.maxHeap.peek();
            if (maxHeapSize == minHeapSize) {
                return (maxHeapHead + minHeapHead) / 2.0;
            }

            return (double) (maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead);
        }

        public static class MaxHeapComparator implements Comparator<Integer> {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        }

        public static class MinHeapComparator implements Comparator<Integer> {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        }
    }


    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    // for test, this method is ineffective but absolutely right
    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        boolean err = false;
//        int testTimes = 200000;
//        for (int i = 0; i != testTimes; i++) {
//            int len = 30;
//            int maxValue = 1000;
//            int[] arr = getRandomArray(len, maxValue);
//            MedianHolder medianHold = new MedianHolder();
//            for (int j = 0; j != arr.length; j++) {
//                medianHold.addNumber(arr[j]);
//            }
//            if (medianHold.getMedian() != getMedianOfArray(arr)) {
//                err = true;
//                printArray(arr);
//                break;
//            }
//        }

        //  System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
        MedianHolder medianHold = new MedianHolder();
        int[] arr = new int[]{1, 2};
        for (int j = 0; j != arr.length; j++) {
            medianHold.addNumber(arr[j]);
        }

        System.out.println(medianHold.getMedian());
    }
}
